#pragma once

#include "LogManagement.h"
#include "MemoryBase.h"
#include "MemoryStack.h"
#include "ContainerBase.h"

#include <assert.h>

namespace EngineLib {

	class _HeapElement {
	public:
		int key;
		void *value;
	};

	template <class T>
	class Heap
	{
	private:
		unsigned int _max_size;
		unsigned int _size;
		_HeapElement *_data;

	public:
		Heap(void) { assert(false); }
		~Heap(void) {}

		static Heap* New(MemoryStack *memoryStack, unsigned int size, MemoryStack::Position left_or_right)
		{
			assert(memoryStack && size);
			unsigned int totalSize = sizeof(Heap<T>) + size * sizeof(_HeapElement);
			Heap<T> *rst = 
				(left_or_right == MemoryStack::LEFT) ?
					((Heap<T>*)memoryStack->AllocateLeft(totalSize)) :
					((Heap<T>*)memoryStack->AllocateRight(totalSize));
			if (!rst) {
				return 0;
			}
			rst->_max_size = size;
			rst->_size = 0;
			rst->_data = (_HeapElement*)(rst + 1) - 1;
			return rst;
		}

		inline bool IsFull(void)
		{
			return _size >= _max_size;
		}

		inline bool IsEmpty(void)
		{
			return _size == 0;
		}

		void Push(int key, T *value)
		{
			if (IsFull()) {
				LogManagement::Error(ERROR_CODE_HEAP_OVERFLOW|ERROR_CODE_FATAL);
				return;
			}

			unsigned int cur = ++_size;
			_HeapElement *parent = &_data[cur/2];

			while ((cur > 1) && (key > parent->key)) {
				_data[cur] = *parent;
				cur /= 2;
				parent = &_data[cur/2];
			}

			_data[cur].key = key;
			_data[cur].value = value;
		}

		T* Top(void)
		{
			return (T*)_data[1].value;
		}

		T* Pop(void)
		{
			if (IsEmpty()) {
				return 0;
			}

			T *rst = Top();

			int key = _data[_size].key;
			unsigned int cur = 1, childIndex = cur * 2;
			_HeapElement *child = &_data[cur * 2];

			--_size;

			while ((childIndex <= _size && key <= child->key) || (childIndex < _size && key <= (child + 1)->key)) {
				if ((child->key > (child + 1)->key) || (childIndex == _size)) {
					_data[cur] = *child;
					cur = childIndex;
				}
				else {
					_data[cur] = *(child + 1);
					cur = childIndex + 1;
				}
				childIndex = cur * 2;
				child = &_data[childIndex];
			}

			_data[cur] = _data[_size + 1];

			return rst;
		}
	};

}